import heapq
from collections import defaultdict, Counter
from copy import deepcopy
PRINT = print
# PRINT = lambda *args: 0

class Heap:
    def __init__(self, lst=None, key=None):
        self.key = key
        lst = lst or []
        if self.key is None:
            self.heap = list(lst)
        else:
            self.heap = [[self.key(x), x] for x in lst]
        heapq.heapify(self.heap)

    def push(self, x):
        if self.key:
            heapq.heappush(self.heap, [self.key(x), x])
        else:
            heapq.heappush(self.heap, x)

    def pop(self):
        if self.key:
            k, x = heapq.heappop(self.heap)
        else:
            x = heapq.heappop(self.heap)
        return x

    def clear(self):
        self.heap.clear()

    def __len__(self):
        return len(self.heap)

    def __getitem__(self, i):
        if self.key:
            return self.heap[i][1]
        else:
            return self.heap[i]


class Helper:
    def __init__(self, m, jobs):
        self.m = m
        self.jobs = jobs
        self.events = defaultdict(list)
        for job, (b, e) in enumerate(jobs):
            self.events[b].append(job)
            self.events[e].append(job)
        self.timeline = sorted(self.events.keys())

    def is_enough(self, k):
        jobs_done_by_worker = [0] * k
        free_workers = Heap(range(k), key=lambda i: jobs_done_by_worker[i])
        hanging_jobs = set()  # {job}
        ongoing_jobs = {}  # {job: worker}
        assignment = [None] * len(self.jobs)
        def get_job_status(job):
            if job in hanging_jobs:
                return 0
            elif job in ongoing_jobs:
                return 1
            else:
                return 2
        for t in self.timeline:
            events = self.events[t]
            events.sort(key=get_job_status)
            for job in events:
                if self.jobs[job][1] == t and job in hanging_jobs:
                    if len(hanging_jobs) < len(free_workers):
                        hanging_jobs.remove(job)
                        worker = free_workers.pop()
                        jobs_done_by_worker[worker] += 1
                        assignment[job] = worker
                        if jobs_done_by_worker[worker] < self.m:
                            free_workers.push(worker)
                        PRINT("time:%d, assign worker %d to job %d and done" % (t, worker, job))
                    elif len(hanging_jobs) == len(free_workers):
                        workers = [free_workers.pop() for _ in range(len(hanging_jobs))]
                        sorted_hanging_jobs = sorted(hanging_jobs, key=lambda job: self.jobs[job][1])
                        hanging_jobs.clear()
                        for i, (worker, job) in enumerate(zip(workers, sorted_hanging_jobs)):
                            jobs_done_by_worker[worker] += 1
                            assignment[job] = worker
                            if i == 0:
                                if jobs_done_by_worker[worker] < self.m:
                                    free_workers.push(worker)
                                PRINT("time:%d, assign worker %d to job %d and done" % (t, worker, job))
                            else:
                                ongoing_jobs[job] = worker
                                PRINT("time:%d, assign worker %d to job %d" % (t, worker, job))
                    else:
                        assert False
                elif self.jobs[job][1] == t and job in ongoing_jobs:
                    worker = ongoing_jobs.pop(job)
                    if jobs_done_by_worker[worker] < self.m:
                        free_workers.push(worker)
                    PRINT("time:%d, worker %d done job %d" % (t, worker, job))
                elif self.jobs[job][0] == t:
                    hanging_jobs.add(job)
                    PRINT("time:%d, job %d starts" % (t, job))
                    if len(hanging_jobs) > len(free_workers):
                        PRINT("time:%d, overflow, hanging_jobs %s, free_workers %s" % (t, hanging_jobs, free_workers.heap))
                        return False
        return True

    def __getitem__(self, x):
        return int(self.is_enough(x))

    def __len__(self):
        return len(self.jobs)


def solve(m, periods):
    import bisect
    helper = Helper(m, periods)
    result = bisect.bisect_left(helper, 1, 0, len(periods) + 1)
    return result


def brutal_is_enough(m, k, jobs):
    n = len(jobs)
    if k >= len(jobs):
        return True
    if m * k < len(jobs):
        return False
    for xx in range(k**n):
        workers = []
        for i in range(n-1, -1, -1):
            workers.append(xx // k**i)
            xx = xx % k**i
        counter = Counter(workers)
        if any(count > m for count in counter.values()):
            continue
        grouped_jobs = defaultdict(list)
        for i, worker in enumerate(workers):
            grouped_jobs[worker].append(i)
        ok = True
        for jobs_ in grouped_jobs.values():
            # sorted_jobs = sorted(jobs_, key=lambda j: jobs[j][0])
            # sorted_jobs = jobs[i] for i in sorted_jobs
            sorted_jobs = [jobs[i] for i in jobs_]
            sorted_jobs.sort()
            if not all(sorted_jobs[i][1] <= sorted_jobs[i+1][0] for i in range(len(sorted_jobs)-1)):
                ok = False
                break
        if ok:
            return True
    return False


# m = 2
# jobs = [[1,2], [2,3], [3,4], [4,5], [5,6]]
# res1 = solve(m, jobs)
# print(res1)


# m = 3
# jobs = [[1, 45], [35, 37], [18, 68]]
# # print(brutal_is_enough(m, 3, jobs))
# print(brutal_is_enough(m, 2, jobs))

# m = 2
# jobs = [[48, 52], [20, 41]] # 2
# print(Helper(m, jobs).is_enough(0))



# m = 2
# jobs = [[5, 93], [19, 63], [19, 91], [29, 53], [57, 61], [66, 78], [68, 93]]  # 4
# helper = Helper(m, jobs)
# print(helper.is_enough(4))
# print(helper.is_enough(5))

m = 2
jobs = [[4, 42], [8, 10], [13, 16], [18, 49], [28, 35], [41, 51]]  # 3
helper = Helper(m, jobs)
print(helper.is_enough(3))
# print(helper.is_enough(2))
# print(brutal_is_enough(m, 3, jobs))
# print(brutal_is_enough(m, 2, jobs))


def random_test():
    import random
    max_time = random.randint(2, 100)
    job_count = random.randint(1, 7)
    m = random.randint(1, job_count)
    jobs = [sorted(random.sample(range(max_time), k=2)) for _ in range(job_count)]
    res1 = solve(m, jobs)
    ok = not brutal_is_enough(m, res1 - 1, jobs) and brutal_is_enough(m, res1, jobs)
    if not ok:
        print(m, jobs, res1)

#
# for _ in range(10000):
#     if _ % 1000 == 0:
#         print(_)
#     random_test()



